var parameter = [];
var LLVPer = []; // list label permanent


var findShortPath = false;

var timeChangeRoute = 15*60;
var velocityBus = 20; // velocity bus = 20km/h
var velocityWalk = 5; // velocity walk = 20km/h

//================================================
var disIncreasePrice;
//================================================

function BinaryHeap(){
  this.dataNext = [];
	this.dataNear = [];
	this.datawalk = [];
	this.LLVTemp = []; // list label temporary

	this.compareOnePriority = function(arrOne, arrTwo) // OK
	{
		switch(parameter[2])
		{
			case 'st':
				if(arrOne[0] > arrTwo[0])
				{
					return 'second';
				}
				else
					return 'first';
			break;
			case 'sd':
				if(arrOne[1] > arrTwo[1])
				{
					return 'second';
				}
				else
					return 'first';
			break;
			case 'sp':
				if(arrOne[2] > arrTwo[2])
				{
					return 'second';
				}
				else
					return 'first';
			break;
		}
	};

	this.compareTwoPriority = function(arrOne, arrTwo) // OK
	{
		switch(parameter[2])
		{
			case 'st':
				if(arrOne[0] > arrTwo[0])
				{
					return 'second';
				}
				else if(arrOne[0] < arrTwo[0])
				{
					return 'first';
				}
				else
				{
					switch(parameter[3])
					{
						case 'sd':
							if(arrOne[1] > arrTwo[1])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						break;
						case 'sp':
							if(arrOne[2] > arrTwo[2])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						break;
					}
				}
			break;
			case 'sd':
				if(arrOne[1] > arrTwo[1])
				{
					return 'second';
				}
				else if(arrOne[1] < arrTwo[1])
				{
					return 'first';
				}
				else
				{
					switch(parameter[3])
					{
						case 'st':
							if(arrOne[0] > arrTwo[0])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						break;
						case 'sp':
							if(arrOne[2] > arrTwo[2])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						break;
					}
				}
			break;
			case 'sp':
				if(arrOne[2] > arrTwo[2])
				{
					return 'second';
				}
				else if(arrOne[2] < arrTwo[2])
				{
					return 'first';
				}
				else
				{
					switch(parameter[3])
					{
						case 'st':
							if(arrOne[0] > arrTwo[0])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						break;
						case 'sd':
							if(arrOne[1] > arrTwo[1])
							{
								return 'second';
							}
							else
							{
								return 'first';
							}
						break;
					}
				}
			break;
		}
	};

	this.compareThreePriority = function(arrOne, arrTwo) // OK
	{
		switch(parameter[2])
		{
			case 'st':
				if(arrOne[0] > arrTwo[0])
				{
					return 'second';
				}
				else if(arrOne[0] < arrTwo[0])
				{
					return 'first';
				}
				else
				{
					switch(parameter[3])
					{
						case 'sd':
							if(arrOne[1] > arrTwo[1])
							{
								return 'second';
							}
							else if(arrOne[1] < arrTwo[1])
							{
								return 'first';
							}
							else
							{
								if(arrOne[2] > arrTwo[2])
								{
									return 'second';
								}
								else
								{
									return 'first';
								}
							}
						break;
						case 'sp':
							if(arrOne[2] > arrTwo[2])
							{
								return 'second';
							}
							else if(arrOne[2] < arrTwo[2])
							{
								return 'first';
							}
							else
							{
								if(arrOne[1] > arrTwo[1])
								{
									return 'second';
								}
								else
								{
									return 'first';
								}
							}
						break;
					}
				}
			break;
			case 'sd':
				if(arrOne[1] > arrTwo[1])
				{
					return 'second';
				}
				else if(arrOne[1] < arrTwo[1])
				{
					return 'first';
				}
				else
				{
					switch(parameter[3])
					{
						case 'st':
							if(arrOne[0] > arrTwo[0])
							{
								return 'second';
							}
							else if(arrOne[0] < arrTwo[0])
							{
								return 'first';
							}
							else
							{
								if(arrOne[2] > arrTwo[2])
								{
									return 'second';
								}
								else
								{
									return 'first';
								}
							}
						break;
						case 'sp':
							if(arrOne[2] > arrTwo[2])
							{
								return 'second';
							}
							else if(arrOne[2] < arrTwo[2])
							{
								return 'first';
							}
							else
							{
								if(arrOne[0] > arrTwo[0])
								{
									return 'second';
								}
								else
								{
									return 'first';
								}
							}
						break;
					}
				}
			break;
			case 'sp':
				if(arrOne[2] > arrTwo[2])
				{
					return 'second';
				}
				else if(arrOne[2] < arrTwo[2])
				{
					return 'first';
				}
				else
				{
					switch(parameter[3])
					{
						case 'st':
							if(arrOne[0] > arrTwo[0])
							{
								return 'second';
							}
							else if(arrOne[0] < arrTwo[0])
							{
								return 'first';
							}
							else
							{
								if(arrOne[1] > arrTwo[1])
								{
									return 'second';
								}
								else
								{
									return 'first';
								}
							}
						break;
						case 'sd':
							if(arrOne[1] > arrTwo[1])
							{
								return 'second';
							}
							else if(arrOne[1] < arrTwo[1])
							{
								return 'first';
							}
							else
							{
								if(arrOne[0] > arrTwo[0])
								{
									return 'second';
								}
								else
								{
									return 'first';
								}
							}
						break;
					}
				}
			break;
		}
	};

  this.compare = function(arrOne, arrTwo) // OK
	{
		switch(parameter.length)
		{
			case 3:
				return this.compareOnePriority(arrOne, arrTwo);
				break;
			case 4:
				return this.compareTwoPriority(arrOne, arrTwo);
				break;
			case 5:
				return this.compareThreePriority(arrOne, arrTwo);
				break;
		}
	};
}

BinaryHeap.prototype = {
  push: function(sCur, tCur, dCur, pCur, rCur, dwCur) {
    // Add the new element to the end of the array.
    if(this.dataNext[sCur])
		{
			var NextTemp = this.dataNext[sCur];
			while(NextTemp.length > 0)
			{
				var timeNext = 0;
				var priceNext = 0;
				var distanceNext = 0;
				if(rCur != NextTemp[0].route)
				{
					// time , price
					priceNext = 4000;
					timeNext = timeChangeRoute;
					//==========================================================================
				  	disIncreasePrice = 0; // increase price from 4000 VND to 7000 VND if > 10 km
				  	//==========================================================================
				}
				priceNext = priceNext + pCur;
				distanceNext = parseInt(NextTemp[0].distance) + dCur;
				timeNext = timeNext + tCur + parseInt((parseInt(3600*NextTemp[0].distance))/(velocityBus*1000));
				var itemLLVTemp = {};
				itemLLVTemp.s = NextTemp[0].next;
				itemLLVTemp.t = timeNext;
				itemLLVTemp.d = distanceNext;
				itemLLVTemp.p = priceNext;
				itemLLVTemp.prevS = sCur;
				itemLLVTemp.r = NextTemp[0].route;
				itemLLVTemp.dw = dwCur;
				this.LLVTemp.push(itemLLVTemp);
				// Allow it to bubble up.
    			this.bubbleUp(this.LLVTemp.length - 1);
				NextTemp.splice(0,1);
			}
		}
		if(this.datawalk.length > 0){
			if(this.dataNear[sCur]){
				var NearTemp = this.dataNear[sCur];
				while(NearTemp.length > 0)
				{
					if(this.datawalk[0] >= parseInt(NearTemp[0].distance))
					{
						var walknext = 0;
						var priceNext = 0;
						var timeNext = 0;
						var distanceNext = 0;
						walknext = dwCur + parseInt(NearTemp[0].distance);
						if(walknext <= this.datawalk[1])
						{
							priceNext = pCur;
							distanceNext = parseInt(NearTemp[0].distance) + dCur;
							timeNext = timeChangeRoute + tCur + parseInt((parseInt(3600*NearTemp[0].distance))/(velocityWalk*1000));
							var itemLLVTemp = {};
							itemLLVTemp.s = NearTemp[0].near;
							itemLLVTemp.t = timeNext;
							itemLLVTemp.d = distanceNext;
							itemLLVTemp.p = priceNext;
							itemLLVTemp.prevS = sCur;
							itemLLVTemp.r = 0;
							itemLLVTemp.dw = walknext;
							this.LLVTemp.push(itemLLVTemp);
							// Allow it to bubble up.
    						this.bubbleUp(this.LLVTemp.length - 1);
						}
					}
					NearTemp.splice(0,1);
				}
			}
		}
  },

  pop: function() {
    // Store the first element so we can return it later.
    var result = this.LLVTemp[0];
    // Get the element at the end of the array.
    var end = this.LLVTemp.pop();
    // If there are any elements left, put the end element at the
    // start, and let it sink down.
    if (this.LLVTemp.length > 0) {
      this.LLVTemp[0] = end;
      this.sinkDown(0);
    }
    return result;
  },

  remove: function(node) {
    var length = this.LLVTemp.length;
    // To remove a value, we must search through the array to find
    // it.
    for (var i = 0; i < length; i++) {
      if (this.LLVTemp[i].s != node.s) continue;
      // When it is found, the process seen in 'pop' is repeated
      // to fill up the hole.
      var end = this.LLVTemp.pop();
      // If the element we popped was the one we needed to remove,
      // we're done.
      if (i == length - 1) break;
      // Otherwise, we replace the removed element with the popped
      // one, and allow it to float up or sink down as appropriate.
      this.LLVTemp[i] = end;
      this.bubbleUp(i);
      this.sinkDown(i);
      break;
    }
  },

  size: function() {
    return this.LLVTemp.length;
  },

  bubbleUp: function(n) {
    // Fetch the element that has to be moved.
    var element = this.LLVTemp[n];
    // When at 0, an element can not go up any further.
    while (n > 0) {
      // Compute the parent element's index, and fetch it.
      var parentN = Math.floor((n + 1) / 2) - 1,
      parent = this.LLVTemp[parentN];
      // If the parent has a lesser score, things are in order and we
      // are done.
      var arrTwo = [parent.t, parent.d, parent.p];
			var arrOne = [element.t, element.d, element.p];
			if(this.compare(arrOne, arrTwo) == 'second')
			{
				break;
			}

      // Otherwise, swap the parent with the current element and
      // continue.
      this.LLVTemp[parentN] = element;
      this.LLVTemp[n] = parent;
      n = parentN;
    }
  },

  sinkDown: function(n) {
    // Look up the target element and its score.
    var length = this.LLVTemp.length;
    var element = this.LLVTemp[n];
    var arrElement = [element.t, element.d, element.p];

    while(true) {
      // Compute the indices of the child elements.
      var child2N = (n + 1) * 2, child1N = child2N - 1;
      // This is used to store the new position of the element,
      // if any.
      var swap = null;
      // If the first child exists (is inside the array)...
      if (child1N < length) {
        // Look it up and compute its score.
        var child1 = this.LLVTemp[child1N];
        var arrChild1 = [child1.t, child1.d, child1.p];
        // If the score is less than our element's, we need to swap.
        if (this.compare(arrElement, arrChild1) == 'second')
          swap = child1N;
      }

      // Do the same checks for the other child.
      if (child2N < length) {
        var child2 = this.LLVTemp[child2N];
        var arrChild2 = [child2.t, child2.d, child2.p];
        if (swap === null) {
        	if (this.compare(arrElement, arrChild2) == 'second') {
        		swap = child2N;
        	}
        } else {
        	var child11 = this.LLVTemp[child1N];
        	var arrChild11 = [child11.t, child11.d, child11.p];
        	if (this.compare(arrChild11, arrChild2) == 'second') {
        		swap = child2N;
        	}
        }
      }

      // No need to swap further, we are done.
      if (swap === null) break;

      // Otherwise, swap and continue.
      this.LLVTemp[n] = this.LLVTemp[swap];
      this.LLVTemp[swap] = element;
      n = swap;
    }
  }
};




var heap = new BinaryHeap();
// =================================================================
function setData(dNext, dNear, inputClient, dwalk)
{
	heap.dataNext = dNext;
	heap.dataNear = dNear;
	heap.datawalk = dwalk;
	parameter = inputClient;
	LLVPer = [];
	heap.LLVTemp = [];
}
function shortTestPath()
{
	// code here
	algorithm();
	if(!findShortPath){
		return null;
	}
	else
	{
		//alert('success');
		var staPrev = LLVPer[LLVPer.length - 1].prevS;
		for(var i = LLVPer.length - 2; i >= 0; i--)
		{
			if(staPrev == LLVPer[i].s)
			{
				staPrev = LLVPer[i].prevS;
			}
			else
			{
				LLVPer.splice(i,1);
			}
		}
	}
	return LLVPer;
}

// =================================================================
function algorithm()
{
	// code here
	setLLVPer(parameter[0], 0, 0, 0, 0, 0, 0);
	var LVTCur = {}; LVTCur.s = parameter[0]; LVTCur.t = 0;
	LVTCur.d = 0; LVTCur.p = 0; LVTCur.r = 0; LVTCur.dw = 0;

	//==========================================================================
  	disIncreasePrice = 0; // increase price from 4000 VND to 7000 VND if > 10 km
  	//==========================================================================

	$i = 0;
	while(true)
	{
		heap.push(LVTCur.s, LVTCur.t, LVTCur.d, LVTCur.p, LVTCur.r, LVTCur.dw);
		var labelTemp = heap.pop();
		if(!labelTemp)
		{
			findShortPath = false;
			break;
		}

		LVTCur.s = labelTemp.s; LVTCur.t = labelTemp.t; LVTCur.d = labelTemp.d;
		LVTCur.p = labelTemp.p; LVTCur.r = labelTemp.r; LVTCur.dw = labelTemp.dw;
		setLLVPer(labelTemp.s, labelTemp.t, labelTemp.d, labelTemp.p, labelTemp.prevS, labelTemp.r, labelTemp.dw);
		heap.remove(labelTemp);
		// condition stop algorithm ================================
		if(LVTCur.s == parameter[1])
		{
			findShortPath = true;	break;
		}
	}
}

function setLLVPer(s, t, d, p, prevS, r, dw) // OK
{
	// code here
	var existLLVPer = false;
	if(LLVPer.length > 0)
	{
		for(var i = 0; i < LLVPer.length; i++)
		{
			if(s == LLVPer[i].s)
			{
				existLLVPer = true;
				break;
			}
		}
	}
	if(!existLLVPer)
	{
		var itemLLVPer = {};
		itemLLVPer.s = s; itemLLVPer.t = t; itemLLVPer.d = d;
		itemLLVPer.p = p; itemLLVPer.prevS = prevS; itemLLVPer.r = r;
		itemLLVPer.dw = dw;		LLVPer.push(itemLLVPer);
	}
}
